Scenarios which require a robot to process, visit, or in some way perform an action over the entirety of a given workspace are known as coverage problems. Common examples of coverage problems include lawn mowing, exploratory mapping, household vacuuming, surveillance, surface painting and de-painting, pesticide spraying, and many others. While these problems have much in common, they also differ in important ways which have considerable impact on the strategies used to optimize and automate their solutions. In the majority of coverage problems, the coverage requirements are discretized into uniformly-sized two- or three-dimensional cells, where each cell represents an area or volume that may require coverage. By using appropriate models, it is possible to estimate which cells will be “covered” by a particular combination of world state, robot state, and robot action. Coverage planners use this estimate along with a hierarchical system of algorithms to determine a sequence of robot actions that efficiently satisfy the coverage requirements while obeying any process-specific constraints.
The nature of these algorithms is strongly influenced by criteria such as the level of environmental uncertainty, environmental and robotic constraints and the nature of the coverage action. Some problems, such as exploratory mapping, operate on a dynamic environment with many unknowns. In these problems, coverage planners must plan adaptively in real time, as the “correct” action changes constantly as new information is discovered. Other problems, such as lawn mowing, operate on a quasi-static environment, allowing robot actions to be planned much farther in advance. Environmental and robotic constraints also significantly affect the types of algorithms used. For example, a slower omnidirectional lawnmower will typically choose a different coverage strategy than a faster mower with nonholonomic steering. An omnidirectional mower may use a simple rectangular graph search algorithm, while a nonholonomic vehicle would tend to use more complex lattice planner.
The nature of the coverage criteria also strongly impacts the type of algorithms considered. A surveillance robot that covers an area by pointing a camera at a location from any of a near infinite number of vantage points will require different planning techniques than a vacuuming robot which covers an area by simply traveling over it.